package demo2;

import java.awt.color.ICC_ColorSpace;

public class Tree {
    static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    //创建二叉树
    public TreeNode creatTree() {
        TreeNode root = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');

        root.left = B;
        root.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        F.left = G;

        return root;
    }

    //前序遍历
    public void preOrder(TreeNode root) {
        if(root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    //中序遍历
    public void inOrder(TreeNode root) {
        if(root == null) {
            return;
        }

        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    //后序遍历
    public void postOrder(TreeNode root) {
        if(root == null) {
            return;
        }

        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

    //求结点总数
    public int size(TreeNode root) {
        if(root == null) {
            return 0;
        }

        return size(root.left) + size(root.right) + 1;
    }

    public static int nodes;
    public void size2(TreeNode root) {
        if(root == null) {
            return;
        }
        nodes++;
        size2(root.left);
        size2(root.right);
    }

    //求叶子结点总数
    public int getLeafNodes(TreeNode root) {
        if(root == null) {
            return 0;
        }
        if(root.left == null && root.right == null) {
            return 1;
        }

        return getLeafNodes(root.left) + getLeafNodes(root.right);
    }

    //求树的高度 = 左子树高度和右子树高度之间的最大值 + 1(根节点)
    public int getTreeHeight(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftHeight = getTreeHeight(root.left);
        int rightHeight = getTreeHeight(root.right);

        return Math.max(leftHeight,rightHeight) + 1;
    }

    //求第k层的结点总数
    public int getKNodes(TreeNode root, int k) {
        if(root == null) {
            return 0;
        }
        if(k == 1) {
            return 1;
        }

        return getKNodes(root.left,k-1) + getKNodes(root.right,k-1);
    }

    //获取val的结点
    public TreeNode getValNode(TreeNode root,char val) {
        if(root == null) {
            return null;
        }
        if(root.val == val) {
            return root;
        }

        TreeNode leftNode = getValNode(root.left,val);
        if(leftNode != null) {
            return leftNode;
        }

        TreeNode rightNode = getValNode(root.right,val);
        if(rightNode != null) {
            return rightNode;
        }

        return null;
    }
}
